数据结构与JavaScript：树Tree的构建教程 |
您所在的位置：网站首页 › js 树形结构 › 数据结构与JavaScript：树Tree的构建教程 |
数据结构与JavaScript：树Tree的构建教程
|
你要创建的东西 树是网络开发中最常用的数据结构之一。这句话对开发者和用户来说都是正确的。每个写过HTML并将其加载到网络浏览器的网络开发者都创建了一棵树，也就是所谓的文档对象模型（DOM）。反过来，每个在互联网上消费信息的用户都以树的形式接收信息，即DOM。 没错，你此刻正在阅读的文章在你的浏览器中是以树的形式呈现的！你正在阅读的段落是以树的形式呈现的。你正在阅读的这段文字在一个 元素中表示出来； 元素嵌套在一个 元素中；而 元素则嵌套在一个 元素中。
数据的嵌套类似于一个家庭树。 元素是一个父元素， 元素是一个子元素，而 元素是 元素的一个子元素。如果这个树的类比对你来说是有用的，那么你会发现，在我们实现树的过程中，会用到更多的类比。 在这篇文章中，我们将使用两种不同的树形遍历方法来创建一棵树：深度优先搜索（DFS）和广度优先搜索（BFS）。(如果你对遍历这个词不熟悉，可以认为它是指访问树的每个节点）。这两种类型的遍历都突出了与树互动的不同方式；此外，这两种旅行都包含了我们在本系列中所涉及的数据结构的使用。DFS使用一个堆栈，BFS使用一个队列来访问节点。这很好! 用深度优先搜索和广度优先搜索遍历一棵树在计算机科学中，树是一种用节点模拟分层数据的数据结构。树的每个节点都持有自己的数据和指向其他节点的指针。 节点和指针的术语对一些读者来说可能是陌生的，所以让我们用一个比喻来进一步描述它们。让我们把树比作一个组织结构图。该图表有一个最高级别的职位（根节点），如CEO。在这个职位的正下方是其他职位，如副总裁（VP）。
为了表示这种关系，我们使用箭头，从CEO指向VP。一个职位，如CEO，是一个节点；我们创建的从CEO到VP的关系是一个指针。为了在我们的组织结构图中创建更多的关系，我们只是重复这个过程--我们让一个节点指向另一个节点。 在概念层面上，我希望节点和指针是有意义的。在实践层面上，我们可以从使用一个更技术性的例子中受益。让我们考虑一下DOM。一个DOM有一个 元素作为它的顶层位置（根节点）。这个节点指向一个 元素和一个 元素。这种结构对DOM中的所有节点都是重复的。 这种设计的优点之一是能够嵌套节点：例如，一个 元素可以有许多 元素嵌套在里面；此外，每个 元素可以有兄弟姐妹的 节点。 深度优先搜索（DFS）深度优先搜索或DFS从初始节点开始，深入到树中，直到找到所需的元素或没有孩子的元素--叶子。然后，它从叶子节点回溯，访问尚未探索的最近的节点。
深度优先搜索 广度优先搜索(BFS)在广度优先搜索中，树的遍历从根节点开始，首先遍历所有邻近的节点。然后，它选择最近的节点并探索新的节点。这种方法对每个节点都是重复的，直到到达目的地。
广度优先搜索 树的操作由于每棵树都包含节点，它可以是树的一个单独的构造器，我们将概述这两个构造器的操作：Node 和Tree 。 节点 data 存储一个值 parent 指向一个节点的父节点 children 指向列表中的下一个节点 树 _root 指向一个树的根节点 find(data)：返回包含给定数据的节点 add(data, parentData): 在父节点上添加一个包含给定数据的新节点 remove(data): 删除包含给定数据的节点 forEach(callback): 在树的每个节点上以深度优先的方式运行一个回调。 forEachBreathFirst(callback): 在树的每个节点上按广度优先的顺序运行回调。 在JavaScript中实现一棵树现在让我们来写一棵树的代码! Node 类对于我们的实现，我们将首先定义一个名为Node 的类，然后定义一个名为Tree 的构造函数。 class Node { constructor(data) { this.data = data; this.parent = null; this.children = []; } }Node的每个实例都包含三个属性。data,parent, 和children 。第一个属性持有与一个节点相关的数据--树的有效载荷。parent 指向这个节点作为其子节点的单一节点。children 指向这个节点的所有子节点。 Tree 类现在，让我们为Tree 定义我们的构造函数，它的定义中包括Node 的构造函数。 class Tree { constructor(data) { let node = new Node(data); this._root = node; } //other Tree methods... }Tree 包含两行代码。第一行是创建一个新的 的实例；第二行是将 指定为树的根。Node node Tree 和Node 的定义只需要几行代码。然而，这些行足以帮助我们模拟分层数据。为了证明这一点，让我们使用一些例子数据来创建一个Tree （以及间接地，Node ）的实例。 let tree = new Tree('CEO'); // {data: 'CEO', parent: null, children: []} tree._root;由于parent 和children 的存在，我们可以添加节点作为_root 的子节点，也可以将_root 指定为这些节点的父节点。换句话说，我们可以模拟分层数据的创建。 Tree的方法接下来，我们将创建以下五个方法。 find(data)：返回包含给定数据的节点 add(data, parentData)：为包含给定数据的父节点添加一个新节点 remove(data)：删除包含给定数据的节点 forEach(callback)：在树的每个节点上以深度优先的方式运行回调。 forEachBreathFirst(callback)：按广度优先的顺序对树的每个节点运行回调。由于添加和删除方法需要我们找到一个特定的节点，我们将从该方法开始，使用深度优先搜索。 深度优先搜索find(data)这个方法用深度优先搜索来遍历一棵树。 //returns the node that has the given data, or null //use a depth-first search find(data, node = this._root) { //if the current node matches the data, return it if (node.data == data) return node; //recurse on each child node for (let child of node.children) { //if the data is found in any child node it will be returned here if (this.find(data, child)) return child; } //otherwise, the data was not found return null; }find() find 是一个递归函数，它有一个参数用于查找数据和要搜索的节点。 也有一个参数用于当前节点--它开始时是树根，后来被用来递归子节点。 for 遍历node 的每个子节点，从第一个子节点开始。在for 循环的主体中，我们用该子节点递归地调用find() 函数。当找到数据时，它将通过整个函数调用的堆栈返回，终止搜索。 如果没有找到匹配的节点，最终将返回null。 请注意，这是一个深度优先的搜索--查找将递归地钻到树的叶子节点，然后再向上钻。 了解递归递归是一个非常难教的话题，需要一整篇文章来充分解释它。由于递归的解释不是本文的重点--重点是实现一棵树--我建议任何对递归缺乏良好掌握的读者用我们的实现find() ，并尝试理解它是如何工作的。 我将在下面附上一个活生生的例子，这样你就可以试试了。 向树中添加元素下面是我们的add 方法的实现。 //create a new node with the given data and add it to the specified parent node add(data, parentData) { let node = new Node(data); let parent = this.find(parentData); //if the parent exists, add this node if (parent) { parent.children.push(node); node.parent = parent; //return this node return node; } //otherwise throw an error else { throw new Error(`Cannot add node: parent with data ${parentData} not found.`); } }add 方法让我们指定新节点的数据，以及我们想将其添加到的父节点。 首先，我们用给定的数据搜索父节点。如果找到了，我们将把新节点添加到父节点的子节点列表中。我们还将把父节点链接到新节点上。现在，新节点被链接到它在树中的位置。 从树上删除元素下面是我们如何实现我们的删除方法。 //removes the node with the specified data from the tree remove(data) { //find the node let node = this.find(data) //if the node exists, remove it from its parent if (node) { //find the index of this node in its parent let parent = node.parent; let indexOfNode = parent.children.indexOf(node); //and delete it from the parent parent.children.splice(indexOfNode, 1); } //otherwise throw an error else { throw new Error(`Cannot remove node: node with data ${data} not found.`); } }就像add 方法一样，首先我们搜索具有给定数据的节点。当我们找到它时，我们可以通过将其从父节点中删除，从而将该节点及其所有的子节点从树上删除。这里我们使用indexOf() ，在父节点的子节点列表中找到该节点，然后我们使用splice() ，将其从该列表中删除。 使用forEach()进行深度优先的树形遍历接下来我们将为我们的树添加一个forEach() 方法，这样我们就可以遍历它，并对每个节点应用一个自定义的回调。 //depth-first tree traversal //starts at the root forEach(callback, node = this._root) { //recurse on each child node for (let child of node.children) { //if the data is found in any child node it will be returned here this.forEach(callback, child); } //otherwise, the data was not found callback(node); }就像find() 方法一样，这是一个深度优先的遍历。 这将访问树中的每一个节点，从第一个分支的底部开始，并通过整个树的方式。想象一下，一只蚂蚁从一片叶子爬上树枝，然后回到另一片叶子，如此循环。 我们可以通过创建一个新的树来测试这个遍历，如下所示。 let t = new Tree("CEO"); t.add("VP Finance", "CEO"); t.add("VP Sales", "CEO"); t.add("Salesperson", "VP Sales"); t.add("Accountant", "VP Finance"); t.add("Bookkeeper", "VP Finance"); t.forEach(node => console.log(node.data));在forEach() ，我们创建了一个简单的回调，在每个节点被访问时将其记录到控制台。如果我们运行这段代码，我们会得到以下输出。 Accountant Bookkeeper VP Finance Salesperson VP Sales CEO 用forEachBreadthFirst()进行广度优先遍历对于大多数用途来说，深度优先搜索更简单，而且同样有效，但有时需要采用广度优先的遍历。这里是我们的Tree 类的最后一个方法。 //breadth-first tree traversal forEachBreadthFirst(callback) { //start with the root node let queue = []; queue.push(this._root); //while the queue is not empty while (queue.length > 0) { //take the next node from the queue let node = queue.shift(); //visit it callback(node); //and enqueue its children for (let child of node.children) { queue.push(child); } } }深度优先遍历使用递归来搜索树，广度优先遍历使用队列结构。当每个节点被访问时，其子节点被推到队列的后面。下一个要访问的节点从队列的前面取走，这就确保了更高层次的节点在其子节点之前被访问。 使用上述相同的树，如果我们用forEachBreadthFirst() 来遍历树，我们将以不同的顺序访问节点。这里是代码。 t.forEachBreadthFirst(node => console.log(node.data));这是它产生的遍历。 CEO VP Finance VP Sales Accountant Bookkeeper Salesperson正如你所看到的，这一次节点被从上到下遍历了。 JavaScript树形结构的交互式例子这里有一个交互式的例子，包含了本帖的所有代码。你可以尝试创建不同的树，并对其进行修改或遍历。 总结树模拟了分层的数据。我们周围的许多世界都类似于这种类型的层次结构，如网页和我们的家庭。任何时候，当你发现自己需要用层次结构来构建数据时，请考虑使用树。 |
.png)
一个HTML页面的文档对象模型@1.25x.png)
组织树.png)
【本文地址】
今日新闻 |
推荐新闻 |